package com.lc.hot100.lc;


public class Main {
	public static void main(String[] args) {
		System.out.println("hello");
	}
}


class Solution1 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        	
        for (int i = 0; i < m; i ++) {
        	for (int j = 0; j < n; j ++) {
        		if (matrix[i][j] == target) {
        			return true;
        		}
        	}
        }
    	
        return false;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
    	int m = matrix.length;
    	int n = matrix[0].length;
    	
    	for (int i = 0; i < m; i ++) {
    		
    		boolean res = search(matrix[i], target);
    		if (res) {
    			return true;
    		}
    		
    	}
    	
    	return false;
    }
    
    
    boolean search(int[] p, int target) {
    	int l = 0, r = p.length - 1;
    	
    	while(l <= r) {
    		int k = (l + r) / 2;
    		if (target == p[k]) {
    			return true;
    		}
    		if (target > p[k]) {
    			l = k;
    		} else {
    			r = k;
    		}
    	}
    	return false;
    }
}